#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

/* 图使用邻接表表示：vector<vector<int>> */

bool topological_sort_by_kahn(vector<vector<int>>& adj, vector<int>& ans) {
    int n = adj.size();
    vector<int> indegree(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < adj[i].size(); j++) {
            indegree[adj[i][j]]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        ans.emplace_back(node);

        for (int neighbor : adj[node]) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    if (ans.size() != n) {
        return false;
    }
    return true;
}

bool dfs(int u, const vector<vector<int>>& adj, vector<int>& visitState, stack<int>& st) {
    visitState[u] = 1;  // 正在访问
    for (int v : adj[u]) {
        if (visitState[v] == 0) {
            if (!dfs(v, adj, visitState, st))
                return false;
        } else if (visitState[v] == 1) {
            // 访问到正在访问的点，说明有环
            return false;
        }
    }
    visitState[u] = 2;  // 访问完成
    st.push(u);
    return true;
}

vector<int> topological_sort_by_dfs(int n, const vector<vector<int>>& adj) {
    vector<int> visitState(n, 0);  // 0: 未访问, 1: 访问中, 2: 已访问
    stack<int> st;

    for (int i = 0; i < n; ++i) {
        if (visitState[i] == 0) {
            if (!dfs(i, adj, visitState, st)) {
                cout << "Graph has a cycle!" << endl;
                return {};  // 有环，返回空
            }
        }
    }

    vector<int> topoOrder;
    while (!st.empty()) {
        topoOrder.push_back(st.top());
        st.pop();
    }

    return topoOrder;
}

int main() {
    vector<vector<int>> adj = {
        {2, 3},    // 0 -> 2, 3
        {3, 4},    // 1 -> 3, 4
        {},        // 2
        {5},       // 3 -> 5
        {5},       // 4 -> 5
        {}         // 5
    };

    vector<int> ans;
    topological_sort_by_kahn(adj, ans);

    for (int num : ans) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}